In order to improve the performance of cache for encrypted data based on Ciphertext Policy Attribute Based Encryption (CP-ABE), an effective replacement algorithm named Minimum Attribute Value (MAV) algorithm was proposed.Combining the access mechanism of ciphertext in CP-ABE and counting the number of high frequency attribute values, the attribute similarity was calculated by using cosine similarity method and the table of high frequency attribute values; meanwhile, the attribute value of each cache file was calculated according to the attribute similarity and size of the encrypted file, then the file with the minimum attribute valuve was replaced. The experimental results prove that the MAV algorithm has better performance in increasing byte hit rate and file request hit rate than the algorithms of Least-Recently-Used (LRU), Least-Frequently-Used (LFU) and Size for encrypted data based on CP-ABE.